package sort;

public class HeapSort {
	private static int[] array;
	private static int size;
	
	public static long Sort(int[] list){
		long startTime = System.currentTimeMillis();
		
		array = new int[list.length+1];
		
		for(int i=0; i<list.length; i++) add(list[i]);
		for(int i=0; i<list.length; i++) list[i] = remove();
		
		return System.currentTimeMillis()-startTime;
	}

	private static void add(int value) {
		array[++size] = value;
		bubbleUp();
	}

	private static int remove() {
		int result = array[1];
		array[1] = array[size--];

		bubbleDown();
		return result;
	}

	private static void bubbleDown() {
		int index = 1, smallerChild;

		while((smallerChild = index<<1) <= size) {
			if(smallerChild+1 <= size && array[smallerChild] > array[smallerChild+1]) smallerChild++;

			if(array[index] > array[smallerChild]) swap(index, smallerChild);
			else break;

			index = smallerChild;
		}        
	}

	private static void bubbleUp() {
		int index = size;

		while(index>1 && array[index>>1] > array[index]) {
			swap(index, index>>1);
			index = index>>1;
		}        
	}

	private static void swap(int index1, int index2) {
		int tmp = array[index1];
		array[index1] = array[index2];
		array[index2] = tmp;        
    }
}